COMMENT ⊗   VALID 00009 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	{[C<NF3αGEOMED.λ30P30I425,0JCFA}  SECTION 3.
C00005 00003		As in  the previous  chapter, the  programming notation  used
C00009 00004	
C00012 00005	[3.1	Euler Routines.]
C00016 00006	{|λ10JAFA}
C00020 00007	[3.2	Euclidean Routines.]
C00023 00008	
C00025 00009	[3.3	Image Synthesis Routines.]
C00027 ENDMK
C⊗;
{[C;<N;F3;αGEOMED.;λ30;P30;I425,0;JCFA}  SECTION 3.
{JCFD} A GEOMETRIC MODELING SYSTEM.
{λ10;W250;JAFA}
	3.0	Introduction to GEOMED.
	3.1	Euler Routines.
	3.2	Euclidean Routines.
	3.3	Image Synthesis Routines.

{λ30;W0;I950,0;JUFA}
[3.0	Introduction to GEOMED.]

	GEOMED  (Geometric Editor)  is a  system  of subroutines  for
manipulating  winged edge  polyhedra. The  system has  two distinctly
different manifestations:  first, it  appears as  an interactive  3-D
drawing  program and  second,   it  appears as  a geometric  modeling
command  language. It is the latter  manifestation along with some of
the details of  implementation that is  the subject of this  chapter.
(GEOMED as  an interactive drawing program is  documented in reference
**). As a language,  GEOMED is all semantics with no particular syntax
of its own. There are about two hundred GEOMED subroutines which take
from  zero to  four arguments,   return  one or  no values  and which
usually have considerable side effects  on the data structures.   The
subroutines can be grouped into four classes: utility routines, Euler
routines,    Euclidean  routines and  image  synthesis  routines. The
utility  routines  (which  will  not  be  further  detailed)  include
input/output,  trigonmetric functions,  memory management,  a command
scanner and  device dependent  display routines.  The Euler  routines
perform  topological operations  on links,    the Euclidean  routines
perform  geometric  computations  on  data  and  the image  synthesis
routines perform photographic simulations on the model as a whole.

	As in  the previous  chapter, the  programming notation  used
will  continue to  have an  ALGOL appearance,   with  specific larger
examples  of actual  GEOMED  code  being  present  embedded  in  SAIL
(Stanford  ALGOL) as  in example  #1 immediately  below. This  simple
GEOMED  program creates two cubic prisms  and displays them rotating.
The header  file, GEOMES.HDR,  is kept on  a disk  area α[GEM,HEα] and
contains the names of the necessary load modules, the declarations of
all the modeling routines and  SAIL macros for accessing GEOMED  data
structures. After the header, the first routine  to execute is MKUNIV
(make  universe), which  initialize the  data  structures.   Next two
blocks  are created  using  the  MKCUBE  routine  which  takes  three
arguments: width, breadth and height of a rectangular parallelepiped.
All  such creation routines  return an integer which  is the absolute
machine address of the GEOMED node of the entity created.

	The next routine used is GEODPY which refreshs the display of
the  model using  default parameters.   Finally,   the  example calls
TRANSL and  ROTATE  which perform  translation and  rotation.  TRANSL
takes four  argument: first  the thing  to be  moved followed  by the
three components of a translation vector; similarly ROTATE takes four
arguments:  first  the thing  to  be  moved  followed  by  the  three
components of a rotation vector.
{λ7;W100;JAF3}
BEGIN "EXAMPLE1"
	REQUIRE "GEOMES.HDRα[GEM,HEα]" SOURCE_FILE;	COMMENT DECLARE GEOMED EMBEDDED IN SAIL;
	DEFINE π="3.1415927";
	INTEGER B1,B2;
	MKUNIV;						COMMENT INITIALIZE THE DATA STRUCTURES;
	B1 ← MKCUBE(2,4,8);				COMMENT CREATE A COUPLE OF CUBIC PRISMS;
	B2 ← MKCUBE(1,2,4);
	TRANSL(B2,-2,2,0);				COMMENT DISPLACE ONE OF THEM;
	WHILE TRUE DO					COMMENT GO FOREVER;
BEGIN
	GEODPY;						COMMENT DISPLAY REFRESH;
	ROTATE(B1,π/10,π/12,π/13);			COMMENT ACTION;
	ROTATE(B2,-π/14,π/16,-π/17);
END;
END "EXAMPLE1";
{λ30;W0;JUFA;}

	Now read Example  #2, immediately below. In this  example the
model of a robot arm is read in and the first three joints are run
through  a simulated  arm  motion.    The  routine  INB3D  reads  B3D
polyhedra files.  The FDNAME, find  name, routine searchs  for GEOMED
body print names,  FDNAME returns zero when a name is not found.  The
routine INCAM  reads in  a camera  file. Finally,  the routine  SHOW2
calls the  hidden line eliminator;  leaving the SHOW2  arguments zero
causes default parameters to be used.

{λ7;W200;JAF3}
BEGIN "EXAMPLE2"
	REQUIRE "GEOMES.HDRα[GEM,HEα]" SOURCE_FILE;
	DEFINE α="COMMENT";
	INTEGER B1,B2,J1,J2,J3,J4,J5,J6,C1,CHR,I;
	MKUNIV;GEODPY;
	B1 ← INB3D("ARMα[DAT,BGBα]");	αα MODEL OF THE YELLOW ARM;
	B2 ← INB3D("TABLEα[DAT,BGBα]");	αα MODEL OF THE HAND/EYE TABLE;
	J1 ← FDNAME("JOINT1");		αα SHOULDER - ABOUT VERTICAL;
	J2 ← FDNAME("JOINT2");		αα ARM - ABOUT HORIZONTAL;
	J3 ← FDNAME("JOINT3");		αα SLIDE;
	J4 ← FDNAME("JOINT4");		αα WRIST TWIST;
	J5 ← FDNAME("JOINT5");		αα WRIST FLAP;
	J6 ← FDNAME("JOINT6");		αα HAND;
	C1 ← INCAM("ARMCAMα[DAT,BGBα]");
	SHOW2(0,0);			αα HIDDEN LINE ELIMINATION;
FOR I←0 THRU 70 DO
BEGIN
	ROTATE(-J1,0,0,π/18);
	ROTATE(-J2,0,0,π/20);
	TRANSL(-J3,0,0,0.1);
	SHOW2(0,0);
END;
END "EXAMPLE2"
{λ30;W0;JUFA;}
[3.1	Euler Routines.]

	The Euler routines  of GEOMED are  based on the idea  that an
arbitrary polyhedron can be created in steps that always maintain the
Euler relation: F-E+V=2*(B-H).   Topologically,   a simply  connected
Eulerian polyhedral  graph can  be built up  with only  four creation
primitives  which I have called:  MKBFV,  MKEV,   MKFE and GLUEE. The
prefixes "MK" and  "KL",  stand for  <make> and <kill>; the  initials
"B",  "F", "E"  and "V"  invariably stand  for <body,  face,  edge> and
<vertex> and tend to appear in  that order. The MKBFV primitives  takes
no arguments and creates a degenerate point polyhedron of one vertex,
one  face  and  one  body  which  is  the  minimal  non-zero  binding
satisfying the Euler equation. The MKEV creates a new edge and  a new
vertex  attached to  the given  vertex in  the given  face. The  MKFE
creates  a new face and a  new edge,  the  new edge is placed between
the two given  vertices. And the GLUEE routine creates  a handle or kills  a body
node by placing a new edge between two given vertices and by removing
the  second  of  two  given  faces.  Complementing  the   make
primitives there are four kill primitives called KLBFEV, KLEV, KLFE
and  UNGLUEE. Completing  the set,  the  ESPLIT routine  (detailed in
section 2.*) is included as a convenient form of MKEV.
The Euler routines and their arguments are summarized in box (3.1).
	
	In principle, the advantages of the pure Euler primitives are
that  they  assure valid  topology,    full generality,    reasonable
simplicity  and they  achieve a  semantic level slightly  higher than
that  of  manipulating  the  polyhedral  nodes  and  links  directly.
However,    the  Euler  primitives  only  satisfy the  first  of  the
conditions  defining  a  solid  polyhedron; imposing  no   particular
restrictions on surface  orientation,  face/vertex trivalence,   face
planarity, face convexity or surface self intersection. In practice,
the Euler  primitives serve as  a topological  foundation for  coding
further routines which embody more algebra and geometry.{Q}
{|;λ10;JAFA}
BOX 3.1 {JC}  TABLE OF EULER ROUTINES

EULER MAKE PRIMITIVES:

   1. 	BNEW ← MKBFV;   	Makes point polyhedron: 1 face, 1 vertex.
   2. 	VNEW ← MKEV(F,V);	Makes new edge and vertex such that:
				VNEW = NVT(ENEW); V = PVT(ENEW);
	VNEW ← ESPLIT(E);	Makes new edge and vertex...
   3. 	ENEW ← MKFE(V1,F,V2);   Makes new face and edge such that:
				FNEW = NFACE(ENEW); F = PFACE(ENEW);
				  V1 = PVT(ENEW);  V2 = NVT(ENEW).
   4. 	ENEW ← GLUEE(F1,V1,F2,V2);	Makes new edge, Kills F2,
				and makes a hole or kills a body.
				  V1 = PVT(ENEW);  V2 = NVT(ENEW).
EULER KILL PRIMITIVES:

   1. 	QNEW ← KLBFEV(Q);	Kills B.F.E.V. entity.
   2. 	   F ← KLFE(E);		Kills E and NFACE(E). Returns PFACE(E).
   3. 	   E ← KLEV(V);		Kills V and PED(V).   Returns other E of V.
	   V ← KLEV(E);		Kills E and NVT(E).   Returns PVT(E).
   4. 	FNEW ← UNGLUE(E);	Kills E; makes F;     Returns the new face,
				and kills a hole or makes a body.

FURTHER EULER ROUTINES:		

   1.	BODY ←	GLUE(FACE1,FACE2);	Removes face1 and face2.
   2.	QNEW ←	MKCOPY(ENTITY);		Copy an entity.
   3.	FACE ←	SWEEP(FACE,FLAG);	Make prism on face (or sweep wire).
   4.	FACE ←	ROTCOM(FACE);		Rotation sweep wire face completion.
   5.	PEAK ←	PYRAMID(FV);		Make pyramid on a face (or vertex).
   6.	BODY ←  FVDUAL(BODY);		Apply face/vertex duality to a body.
   7.	BNEW ←  MKCUBE(DX,DY,DZ);	Create right rectangular prism.
   8.	BNEW ←  MKCYLN(RADIUS,N,DZ);	Create cylinder approximation.
   9.	BNEW ←  MKBALL(RADIUS,M,N);	Create sphere approximation.

{|;λ30;JU;FA}
{Q}
[3.2	Euclidean Routines.]

	The  Euclidean routines  of  GEOMED  fall into  four  groups:
transformations,  metrics, frame routines and space simulators.
The  Euclidean transformation  primitives are  translation, rotation,
dilation and reflection (following  Klein's Erlangen Program,  1872).
The  Euclidean  metric  routines compute  distances,  angles,  areas,
volumes and inertia tensors; while the frame routines create or alter
frame nodes which are explained below. The final group of routines
are for spatial simulations such as collision, propinquity, occupancy
and occultation. The calling format of the basic Euclidean routines of each group
are summarized in box (3.2).

	Fundamental to the frame routines is the curious fact that a
frame  node has  two interpretations:  it may  be used  to  specify a
coordinate systems  or  it  may  be used  to  represent  a  Euclidean
transformation. It is a pity that the term <frame> is becoming over used in
Artificial Intelligence; the present context is as in a <frame of reference>
or <coordinate frame>.
	
	The Euclidean routines  involving frames can be  explained in
terms of  the 4-D homogeneous coordinates  found in computer graphics
then both frames of reference  and transformations can be viewed as  a
tensor. A <tensor> is a coordinate independent multi linear function.

{Q;|;λ10;JAFA}
BOX 3.2 {JC}  TABLE OF EUCLIDEAN ROUTINES.

EUCLIDEAN TRANSFORMATIONS
	TRANS	←	TRANSL(XWD(FRAME,BODY),DX,DY,DZ);
	TRANS	←	ROTATE(XWD(FRAME,BODY),WX,WY,WZ);
	TRANS	←	SHRINK(XWD(FRAME,BODY),KX,KY,KZ);
	TRANS	←	APTRAN(ENTITY,TRANS);
	TRANS	←	INTRAN(TRAN);

FRAME ROUTINES
	TRANS	←	MKROT1(PAN,TILT,SWING);		MAKE FROM EULER ANGLES.
	TRANS	←	MKFFRM(FACE);			MAKE FACE FRAME.
	TRANS	←	MKQFRM(WX,WY,WZ);		MAKE FROM ROTATION VECTOR.
	NORM(FRAME)	;NORMALIZATION TO UNIT VECTORS.
	ORTHO1(FRAME)	;ORTHOGONALIZE BY WORST CASE.
	ORTHO2(FRAME)	;ORTHOGONALIZE BY K ← (I CROSS J), J ← (K CROSS I).

METRIC ROUTINES.
	DETERM(FRAME)
	ANGL3V(V1,V2,V3)
	DISTANCE(ENTITY,ENTITY);

SPATIAL SIMULATIONS.

{|;λ10;JU;FA}

[3.3	Image Synthesis Routines.]

	The image  synthesis includes perspective  projection, hidden
line   elimination,   Z-clipping,   display  window   transformation,
XY-clipping and the generation of  a video file, or a vector  display
file or some other disirable image data structure.

	The perspective projection takes the 3-D world locus of every
potentially visible vertex and computes a 3-D camera center coordinate locus
followed by a perspective projection.

	
;PERSPECTIVE TRANSFORMATION.
	XPP(V) ← SCALEX * XCC/ZCC;	α  where   SCALEX = -FOCAL/PDX;
	YPP(V) ← SCALEY * YCC/ZCC;	α  where   SCALEY = -FOCAL/PDY;
	ZPP(V) ← SCALEZ      /ZCC;	α  where   SCALEZ = -FOCAL/PDZ;

	ZPP(V) IS POSITIVE WHEN VERTEX IS INVIEW.   ←←← NOTA BENE.